package main

// 200. 岛屿数量
func main() {
	grid := [][]byte{
		{1, 1, 1, 1, 0},
		{1, 1, 0, 1, 0},
		{1, 1, 0, 0, 0},
		{0, 0, 0, 0, 0},
	}

	//grid = [][]byte{
	//	{1, 1, 0, 0, 0},
	//	{1, 1, 0, 0, 0},
	//	{0, 0, 1, 0, 0},
	//	{0, 0, 0, 1, 1},
	//}
	islands := numIslands(grid)
	println(islands)
}

func numIslands(grid [][]byte) int {
	// dfs
	X := len(grid)    // 高
	Y := len(grid[0]) // 宽

	landsNum := 0

	var dfs func(x, y int)
	dfs = func(x, y int) {
		if x < 0 || x >= X || y < 0 || y >= Y {
			return
		}
		if grid[x][y] == 2 || grid[x][y] == 0 {
			return
		}
		grid[x][y] = 2

		dfs(x+1, y)
		dfs(x, y+1)
		dfs(x-1, y)
		dfs(x, y-1)
	}

	for i := 0; i < X; i++ {
		for j := 0; j < Y; j++ {
			if grid[i][j] == 1 {
				landsNum++
				dfs(i, j)
				printByte(grid)
			}
		}
	}

	return landsNum
}

func printByte(grid [][]byte) {
	if len(grid) == 0 || len(grid[0]) == 0 {
		return
	}
	x := len(grid)
	y := len(grid[0])
	for i := 0; i < x; i++ {
		for j := 0; j < y; j++ {
			print(grid[i][j], ",")
		}
		println()
	}
}

// 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
//
//岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
//
//此外，你可以假设该网格的四条边均被水包围。
//
//
//
//示例 1：
//
//输入：grid = [
//  ["1","1","1","1","0"],
//  ["1","1","0","1","0"],
//  ["1","1","0","0","0"],
//  ["0","0","0","0","0"]
//]
//输出：1
//示例 2：
//
//输入：grid = [
//  ["1","1","0","0","0"],
//  ["1","1","0","0","0"],
//  ["0","0","1","0","0"],
//  ["0","0","0","1","1"]
//]
//输出：3
//
//
//提示：
//
//m == grid.length
//n == grid[i].length
//1 <= m, n <= 300
//grid[i][j] 的值为 '0' 或 '1'

////200. 岛屿数量
//
//// 200. 岛屿数量
//func numIslands(grid [][]byte) int {
//	var res int
//	if len(grid) == 0 || len(grid[0]) == 0 {
//		return res
//	}
//	height := len(grid)
//	width := len(grid[0])
//
//	for i := 0; i < height; i++ {
//		for j := 0; j < width; j++ {
//			if grid[i][j] == 1 {
//				res++
//				dfs(grid, i, j)
//			}
//		}
//	}
//
//	return res
//}
//
//// 使用递归的方式查询
//
//func dfs(grid [][]byte, row, column int) {
//	if len(grid) == 0 || len(grid[0]) == 0 {
//		return
//	}
//	height := len(grid) - 1
//	width := len(grid[0]) - 1
//	if row < 0 || column < 0 || row > height || column > width || grid[row][column] == 0 {
//		return
//	}
//	grid[row][column] = 0
//	dfs(grid, row-1, column)
//	dfs(grid, row+1, column)
//	dfs(grid, row, column-1)
//	dfs(grid, row, column+1)
//}
